As a coding method for a moving picture, standard moving picture coding methods such as ITU-T H.26x and MPEG series have been heretofore known. In these moving picture coding methods, predetermined data transform operations such as motion compensation (MC) and discrete cosine transform (hereinafter referred to as DCT) are performed for respective images of blocks obtained by dividing a frame image. Thus, image data that is a coded object is prepared.
The image data prepared by the data transform operations further undergoes variable-length coding, and becomes coded data that is compressed data used for an image transfer. As one of such variable-length coding methods, an arithmetic coding (AC) has been used.
In general, in the case of carrying out the arithmetic coding of an information source string (symbol string) formed by combining plural types of symbols, first, certain sections are allocated to the respective symbols in accordance with the appearance probabilities of the symbols on a number line (probability number line) of [0.0, 1.0). In this case, one representing correspondence relationships between the symbols and the sections on the number line is called a probability table. When the information source string undergoes the variable-length coding by the arithmetic coding, code words expressing the information source string on the number line is generated by referring to this probability table.
Here, the arithmetic coding will be described with reference to FIGS. 1 to 3. Specifically, a character string “ARITHMETIC” will be cited as the information source string to be coded, and the arithmetic coding thereof will be exemplified.
Eight types of characters (symbols), which are A, C, E, H, I, M, R and T, appear in the above-described information source string. As shown in the table of FIG. 1, sections are allocated to these characters on the number line (probability number line) of [0.0, 1.0) such that section lengths proportional to the appearance probabilities of the respective characters in the character string can be obtained. The table shown in FIG. 1, which represents these correspondence relationships between the characters and the sections on the number line, becomes a probability table for use in the arithmetic coding.
FIG. 2 is a diagram illustrating the coding of the character string “ARITHMETIC” by use of the probability table shown in FIG. 1. In the arithmetic coding, a section reduction operation based on the probability table is sequentially carried out for the respective symbols included in the information source string, thus generating code words formed by coding the information source string.
In the example shown in FIG. 2, first, the probability table shown in FIG. 1 is referred to for the first character “A” of the character string “ARITHMETIC” to be coded, and the section [0, 1) on the number line is divided into eight sections corresponding to the respective characters. Then, the section is reduced to the section [0.0, 0.1) corresponding to the character “A” among the eight sections. Next, the probability table is referred to for the second character “R”, and the section [0.0, 0.1) is divided into eight sections. Subsequently, among these sections, the section is reduced to the section [0.07, 0.08) corresponding to the character “R”.
Hereinafter, the coding operations by the section reduction are carried out sequentially for each of the characters. Then, in the section [0.0757451536, 0.0757451552) on the number line finally obtained, a numerical value “0.0757451536” within the section is generated as a code word obtained by performing the arithmetic coding of the character string “ARITHMETIC”.
FIG. 3 is a table showing decoding of the code word “0.0757451536” obtained by use of the probability table shown in FIG. 1 to the character string “ARITHMETIC”.
In the example shown in FIG. 3, the probability table shown in FIG. 1 is referred to for the code word “0.0757451536” to be decoded, and the section [0.0, 0.1) having a section length of 0.1 in which the code word is included is specified. Then, the character “A” corresponding to the specified section is outputted as the first character, and a new code word “0.757451536” is generated by (code word—lower limit)/(section length). Next, the probability table is referred to for the code word “0.757451536”, and a section [0.7, 0.8) having a section length of 0.1 in which the code word is included is specified. Then, the character “R” corresponding to the specified section is outputted as the second character, and a new code word “0.57451536” is generated.
Hereinafter, the decoding operations are sequentially carried out for the code words. Then, the character string “ARITHMETIC” is restored from the code word “0.0757451536” which underwent the arithmetic coding.
As described above, in the variable-length coding of the information source string by use of the arithmetic coding, the symbols included in the information source string and the sections on the number line are allowed to correspond to each other, thus making it possible to express an arbitrary information source string by the code words on the number line of [0.0, 1.0). Moreover, the probability table allowing the symbols and the sections to correspond to each other is set in accordance with the appearance probabilities of the respective symbols, whereby the variable-length coding of the information source string can be performed effectively and the efficiency of data compression by the coding can be enhanced.